package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * 打印出所有值为 sum 的路径
 *
 * @author zk
 */
public class PathSum2 {

    // =================
    // DFS 算法
    // =================

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null)
            return resultList;

        // 或许 currentPath 改成 Stack 更好
        List<Integer> currentPath = new ArrayList<>();
        pathSumInner(root, sum, currentPath, resultList);
        return resultList;
    }

    public void pathSumInner(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result) {
        // push 这个节点
        path.add(root.val);

        if (root.left == null && root.right == null && sum - root.val == 0)
            result.add(new ArrayList<>(path));

        if (root.left != null)
            pathSumInner(root.left, sum - root.val, path, result);

        if (root.right != null)
            pathSumInner(root.right, sum - root.val, path, result);

        // pop 这个节点
        path.remove(path.size() - 1);
    }

    public static void main(String...args) {
        System.out.println(new PathSum2().pathSum(TreeFactory.buildTree(new Integer[]{
                5,
                4,8,
                11,null,13,4,
                7,2,null,null,5,1
        }), 22));
    }

}
